#define _CRT_SECURE_NO_WARNINGS 1


//#include <stdio.h>
//#include <stdlib.h>
//#include <assert.h>
//#include <stdbool.h>
//
//typedef int STDataType;
//
//typedef struct stack
//{
//	STDataType* a;
//	int top;
//	int capacity;
//}ST;
//
//void STInit(ST* ps)
//{
//	assert(ps);
//
//	ps->a = NULL;
//	ps->top = 0;
//	ps->capacity = 0;
//}
//
//void STDestroy(ST* ps)
//{
//	assert(ps);
//
//	free(ps->a);
//	ps->a = NULL;
//	ps->top = 0;
//	ps->capacity = 0;
//}
//
//bool STEmpty(ST* ps)
//{
//	assert(ps);
//
//	return 0 == ps->top;
//}
//
//int STSize(ST* ps)
//{
//	assert(ps);
//
//	return ps->top;
//}
//
//void STPush(ST* ps, STDataType x)
//{
//	assert(ps);
//
//	if (ps->top == ps->capacity)
//	{
//		int newcapacity = 0 == ps->capacity ? 4 : 2 * ps->capacity;
//		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
//
//		if (NULL == tmp)
//		{
//			perror("realloc fail");
//			return;
//		}
//
//		ps->a = tmp;
//		ps->capacity = newcapacity;
//	}
//
//	ps->a[ps->top] = x;
//	ps->top++;
//}
//
//void STPop(ST* ps)
//{
//	assert(ps);
//	assert(!STEmpty(ps));
//
//	ps->top--;
//}
//
//STDataType STTop(ST* ps)
//{
//	assert(ps);
//	assert(!STEmpty(ps));
//
//	return ps->a[ps->top - 1];
//}
//
//typedef struct
//{
//	ST pushst;
//	ST popst;
//} MyQueue;
//
//
//MyQueue* myQueueCreate()
//{
//	MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
//	STInit(&obj->pushst);
//	STInit(&obj->popst);
//
//	return obj;
//}
//
//void myQueuePush(MyQueue* obj, int x)
//{
//	assert(obj);
//
//	STPush(&obj->pushst, x);
//}
//
//bool myQueueEmpty(MyQueue* obj)
//{
//	assert(obj);
//
//	return STEmpty(&obj->pushst) && STEmpty(&obj->popst);
//}
//
//int myQueuePeek(MyQueue* obj)
//{
//	assert(obj);
//	assert(!myQueueEmpty(obj));
//
//	if (STEmpty(&obj->popst))
//	{
//		while (!STEmpty(&obj->pushst))
//		{
//			STDataType top = STTop(&obj->pushst);
//			STPush(&obj->popst, top);
//			STPop(&obj->pushst);
//		}
//	}
//
//	return STTop(&obj->popst);
//}
//
//int myQueuePop(MyQueue* obj)
//{
//	STDataType front = myQueuePeek(obj);
//	STPop(&obj->popst);
//	return front;
//}
//
//void myQueueFree(MyQueue* obj)
//{
//	assert(obj);
//
//	STDestroy(&obj->pushst);
//	STDestroy(&obj->popst);
//	free(obj);
//}



#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef int QDataType;

typedef struct QueueNode
{
	QDataType x;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

void QueueInit(Queue* obj)
{
	assert(obj);

	obj->phead = NULL;
	obj->ptail = NULL;
	obj->size = 0;
}

void QueueDestroy(Queue* obj)
{
	assert(obj);

	QNode* cur = obj->phead;

	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	obj->phead = obj->ptail = NULL;
	obj->size = 0;
}

int QueueSize(Queue* obj)
{
	assert(obj);

	return obj->size;
}

bool QueueEmpty(Queue* obj)
{
	assert(obj);

	return 0 == obj->size;
}

void QueuePush(Queue* obj, QDataType x)
{
	assert(obj);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));

	if (NULL == newnode)
	{
		perror("malloc fail");
		return;
	}

	newnode->x = x;
	newnode->next = NULL;

	if (QueueEmpty(obj))
	{
		obj->phead = obj->ptail = newnode;
	}
	else
	{
		obj->ptail->next = newnode;
		obj->ptail = newnode;
	}

	obj->size++;
}

void QueuePop(Queue* obj)
{
	assert(obj);
	assert(!QueueEmpty(obj));

	QNode* next = obj->phead->next;
	free(obj->phead);
	obj->phead = next;
	obj->size--;
}

QDataType QueueFront(Queue* obj)
{
	assert(obj);
	assert(!QueueEmpty(obj));

	return obj->phead->x;
}

QDataType QueueBack(Queue* obj)
{
	assert(obj);
	assert(!QueueEmpty(obj));

	return obj->ptail->x;
}


typedef struct
{
	Queue q1;
	Queue q2;
} MyStack;


MyStack* myStackCreate()
{
	MyStack* obj = (MyStack*)malloc(sizeof(MyStack));

	QueueInit(&obj->q1);
	QueueInit(&obj->q2);

	return obj;
}

void myStackPush(MyStack* obj, int x)
{
	assert(obj);

	if (!QueueEmpty(&obj->q1))
	{
		QueuePush(&obj->q1, x);
	}
	else
	{
		QueuePush(&obj->q2, x);
	}
}

bool myStackEmpty(MyStack* obj)
{
	return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

int myStackPop(MyStack* obj)
{
	assert(obj);
	assert(!myStackEmpty(obj));

	Queue* Qempty = &obj->q1;
	Queue* Qnonempty = &obj->q2;

	if (!QueueEmpty(&obj->q1))
	{
		Qempty = &obj->q2;
		Qnonempty = &obj->q1;
	}

	while (QueueSize(Qnonempty) > 1)
	{
		QDataType front = QueueFront(Qnonempty);
		QueuePush(Qempty, front);
		QueuePop(Qnonempty);
	}

	int top = QueueFront(Qnonempty);
	QueuePop(Qnonempty);
	return top;
}

int myStackTop(MyStack* obj)
{
	assert(obj);
	assert(!myStackEmpty(obj));
	
	if (!QueueEmpty(&obj->q1))
	{
		return QueueBack(&obj->q1);
	}
	else
	{
		return QueueBack(&obj->q2);
	}
}

void myStackFree(MyStack* obj)
{
	assert(obj);

	QueueDestroy(&obj->q1);
	QueueDestroy(&obj->q2);
	free(obj);
}